// https://leetcode.cn/problems/longest-increasing-subsequence/submissions/498301113/

// 

function lengthOfLIS(nums: number[]): number {

    const n = nums.length;

    // 记录每个组的最小值
    const tails : number[] = [];
    
    //遍历每一个元素
    for(let i = 0; i < n; i++) {

        const num = nums[i];
        let left = 0;
        let right = tails.length - 1;

        while(left <= right) {
            let mid =  Math.floor((left + right)/2);
            if(tails[mid] >= num){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        // 这个数非常的大，没有找到插入的位置，则在结果追加
        if (left === tails.length) {
            tails.push(num);
        }else{
            tails[left] = num; // 覆盖之前的值
        }
    }

    return tails.length;
};

export {}